Federated computing infrastructures such as Computational Grids and service overlay networks (“SON”) have become increasingly important to many emerging applications such as web service composition, distributed stream processing, and workflow management. As these computing infrastructures continue to grow, the efficient management of such large-scale dynamic distributed systems to better support application needs has become a challenging problem. Distributed information management services (which are further described in Robbert van Renesse, Kenneth Birman and Werner Vogels. Astrolab: A robust and scalable technology for distributed system monitoring, management, and data mining. ACM Transactions on Computer Systems, 21(2):164-206, May 2003; P. Yalagandula and M. Dahlin. A Scalable Distributed Information Management System. Proc. of SIGCOMM 2004, August 2004; and David Oppenheimer, Jeannie Albrecht, David Patterson and Amin Vahdat. Design and implementation trade-offs for wide area resource discovery. In HPDC-14, July 2005, respectively, and are herein incorporated by reference in their entireties) is one of the fundamental building blocks of system management, which can track dynamic system information and make it available via some query interfaces.
Applications running in the distributed environment can then query the current status of the system and make appropriate management decisions. For example, when a new application needs to be executed on a Grid system, a query “find 10 machines that have at least 20% free CPU time, 20 MB memory, and 2G disk space” can be issued to discover necessary resources.
However, providing scalable and efficient information management service for large-scale, dynamic distributed systems such as SONs is a challenging task. On one hand, quality sensitive applications running in such environment desire up-to-date information about the current system in order to better accomplish their application goals. On the other hand, the system can include a large number of geographically dispersed nodes (e.g., the World Community Grid consists of many thousands of nodes), and each node can be associated with many dynamic attributes (e.g., CPU load, memory space, disk storage, and other application level attributes). Obtaining accurate information about all nodes with their complete information inevitably involves high system overhead.
Distributed information management is critical for any large-scale system management infrastructure. For example, both the CoMon PlanetLab monitoring service and the Grid Monitoring/Discovery Service, (which are further described in K. Park and V. S. Pai. Comon: A mostly-scalable monitoring system for planetlab. Operating Systems Review, Vol 40, No 1, January 2006, and K. Czajlowski, S. Fitzgerald, I. Foster, and C. Kesselman. Grid information services for distributed resource sharing. In HPDC-10, 2001, respectively, and are herein incorporated by reference in their entireties), have proven extremely useful for their user communities. However, both systems are statically configured. Every node pushes all attribute data to a central server at fixed intervals, even when the attribute data are unlikely to satisfy application queries.
Astrolabe and SDIMS, (which are further described in enter Robbert van Renesse, Kenneth Birman and Werner Vogels. Astrolab: A robust and scalable technology for distributed system monitoring, management, and data mining. ACM Transactions on Computer Systems, 21(2):164-206, May 2003; P. Yalagandula and M. Dahlin. A Scalable Distributed Information Management System. Proc. of SIGCOMM 2004, August 2004, respectively, and are herein incorporated by reference in their entireties), are two representative scalable distributed information management systems. The primary focus of these systems is aggregation queries such as MIN, MAX, and SUM.
Other systems such as Mercury, SWORD and PIER, (which are further described in Ashwin R. Bharambe, Mukesh Agrawal, and Srinivasan Seshan. Mercury: Supporting scalable multi-attribute range queries. In SIGCOMM 2004, August 2004; David Oppenheimer, Jeannie Albrecht, David Patterson and Amin Vahdat. Design and implementation trade-offs for wide area resource discovery. In HPDC-14, July 2005, and Ryan Huebsch, Joseph M. Hellerstein, Nick Lanham, Boon Thau Loo, Scott Shenker and Ion Stoica. Querying the internet with PIER. In Proceedings of 29th VLDB Conference, 2003, respectively, and are herein incorporated by reference in their entireties), can support multi-attribute queries. However, their focus is on how to resolve queries in different decentralized architectures.
Additionally, there has been work on query pattern/workload estimation (such as that described in N. Bruno, S. Chaudhuri, and L. Gravano. Stholes: A multidimensional workload-aware histogram. In ACM SIGMOID 2001, May 2001, and Yi-Leh Wu, Divyakant Agrawal, and Amr El Abbadi. Query estimation by adaptive sampling. In 18th International Conference on Data Engineering (ICDE'02), 2002, which are hereby incorporated by reference in their entireties), in the database community. The goal is often to build appropriate histograms to estimate the data distribution, so that different query plans can be evaluated more accurately.
Therefore a need exists to overcome the problems with the prior art as discussed above.